package psn.zjk.career.interview.algorithm.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 * 注意: * 你可以假设树中没有重复的元素。
 *
 * @author zhangjk
 * @CREATE_TIME 2021/2/18 16:48
 */
public class LeetCode105 {

    /** 思路：前序遍历+中序遍历可以确定唯一一棵二叉树，递归将两个数组分区，返回分区的根节点 */

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        //前序遍历：根，左节点集，右节点集
        //中序遍历：左节点集，根，右节点集
        TreeNode root = new TreeNode(preorder[preStart]);
        Integer rootIndex = map.get(root.val);
        int numOfLeftNodes = rootIndex - inStart;
        //2.左
        TreeNode left = build(preorder, preStart + 1, preStart + 1 + numOfLeftNodes, inorder, inStart, rootIndex - 1, map);
        //3.右
        TreeNode right = build(preorder, preStart + numOfLeftNodes + 1, preEnd, inorder, rootIndex + 1, inEnd, map);
        return new TreeNode(preorder[preStart], left, right);
    }


    public static void main(String[] args) {
        int[] x = {3, 9, 20, 15, 7};
        int[] z = {9, 3, 15, 20, 7};
        TreeNode treeNode = new LeetCode105().buildTree(x, z);
        System.out.println(treeNode);

    }

}